package leetcode1;

import java.util.*;

public class Day16 {

    public static void main(String[] args) {
        //int[][] nums = {{1,3},{2,6},{8,10},{15,18}};
        int[][] nums = {{1,4}};
        merge(nums);
    }

    public static int[][] merge2(int[][] intervals) {
        //1.排序
        Arrays.sort(intervals,(a,b)-> {
            return a[0] - b[0];
        });
        //2.合并
        List<int[]> list = new ArrayList<>();
        int left=intervals[0][0],right=intervals[0][1];
        for(int i=1;i<intervals.length;i++) {
            int a=intervals[i][0],b=intervals[i][1];
            if(right >= a) {
                //可以合并
                right = Math.max(right,b);
            }else {
                list.add(new int[]{left,right});
                left = a;
                right = b;
            }
        }
        list.add(new int[]{left,right});
        //3.返回
        return list.toArray(new int[0][]);
    }

    public static int[][] merge(int[][] intervals) {
        int n=intervals.length,m=intervals[0].length;//行、列
        if(n <= 1) {
            int[][] nums = {{1,4}};
            nums[0][0]=intervals[0][0];
            nums[0][1]=intervals[0][1];
            return nums;
        }
        //1.排序二维数组，按照左端点
        Arrays.sort(intervals,(a,b)-> {
            return a[0] - b[0];
        });
        //2.合并区间
        Queue<int[]> q = new LinkedList<>();
        int i=0;
        int k=0;
        while (i<n){
            int left=intervals[i][0],right=intervals[i][m-1];
            int[] tmp = new int[2];
            tmp[0]=left;tmp[1]=right;
            i++;
            int a=0,b=0;
            if(i<n) {
                a=intervals[i][0];
                b=intervals[i][m-1];
            }
            while (i<n && right >= a) {
                //合并区间
                right = Math.max(right,b);
                i++;
                if(i<n) {
                    a=intervals[i][0];b=intervals[i][m-1];
                }
            }
            tmp[1]=right;
            q.add(tmp);
            k++;
        }
        //3.取出结果
        int[][] ret = new int[k][2];
        for (int j = 0; j < k; j++) {
            int[] tmp = new int[2];
            tmp = q.poll();
            ret[j][0]=tmp[0];
            ret[j][1]=tmp[1];
        }
        return ret;
    }
}
